/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\923.三数之和的多种可能.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-27 16:32:03
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-27 16:40:35
 */
/*
 * @lc app=leetcode.cn id=923 lang=cpp
 *
 * [923] 三数之和的多种可能
 */

// @lc code=start
class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        sort(arr.begin(),arr.end());
        int first;
        int long count = 0;
        int n = arr.size();
        for(first = 0 ; first < n ; first++)
        {
            int second = first + 1;
            int third = n - 1;
            while(second < third)
            {
                int Sum = arr[first] + arr[second] + arr[third];
                if(Sum == target)
                {
                    count++;
                    second++;
                    continue;
                }
                else if(Sum > target)
                {
                    third--;
                }else if(Sum < target)
                {
                    second++;
                }
            }
        }

        return count % (10^9 + 7);
    }
};
// @lc code=end

